/****************************************************************************
 * Elisa 1.0                                                                *
 *--------------------------------------------------------------------------*
 * Author: Laurent Granvilliers, Vincent Sorin                              *
 * Copyright (c) 2004 Laboratoire d'Informatique de Nantes Atlantique       *
 *--------------------------------------------------------------------------*
 * Elisa is distributed WITHOUT ANY WARRANTY. Read the associated           *
 * COPYRIGHT file for more details.                                         *
 *--------------------------------------------------------------------------*
 * elisa_solver.h                                                           *
 ****************************************************************************/

/**
 * @file elisa_solver.h
 * @brief Classes for search algorithms.
 */

/**
 * @defgroup Search Search
 * @brief Classes for search algorithms.
 */

#ifndef _ELISA_SOLVER_H
#define _ELISA_SOLVER_H

#include <list>
#include <memory>
#include <fstream>
#include <boost/bind.hpp>

#include "elisa_defs.h"
#include "elisa_variable.h"
#include "elisa_reduction.h"
#include "elisa_search_strategy.h"
#include "elisa_search_output.h"
#include "elisa_model.h"

NAMESPACE_ELISA

/**
 * @class Strategy
 * interface for interacting with a SearchTree 
 * (e.g. making the neighborhood, backtrack, move)
 */
class Strategy
{
public:
	/**
 	 * do the action
 	 */
	virtual bool operator()() = 0;

	SearchTree *m_st;
};

typedef std::auto_ptr<Strategy> StrategyPtr;

/**
 * @class BackTrack
 * strategy to do backtracking in the SearchTree
 */
class BackTrack : public Strategy
{
public:
	/**
 	 * strategy algorithm
 	 */
	virtual bool operator()()
	{
		m_st->getCurrent()->hasBeenExplored();

		if (m_st->getCurrent()->goBack()) {
			Node *n = m_st->getCurrent();
			if (n->getNumUnexploredChildren() != 0) {
				return true;
			} else {
				(*this)();
			}
		}
		return false;
	}
};

/**
 * @class Move
 * move to the first unexplored child
 */
class Move : public Strategy
{
public:
	/**
 	 * strategy algorithm
 	 */
	virtual bool operator()()
	{
		Node *n = m_st->getCurrent();
		if (n->getNumUnexploredChildren() != 0) {
			n->goChild(n->getUnexploredChildren()[0]);
			return true;
		} else {
			return false;
		}
	}
};

/**
 * @class MakeNeighborhood
 */
class MakeNeighborhood : public Strategy
{
public:
	/**
 	 * Make the neighbors of this box
 	 */
	virtual bool operator()()
	{
		m_sc->get()->split();
		//m_sc->get()->split3();
		return true;
	}

	SplitChooserPtr m_sc;
};


/**
 * @ingroup Search
 * @class Solver
 * @brief Branch-and-prune algorithm
 */
class Solver
{
public:
	/**
 	 * Constructor, where each solver is associated to a model
 	 * @param mo the model
 	 */
	Solver(Model *mo, 
		   BackTrack *backTrack = new BackTrack,
		   Move *move = new Move(), 
		   MakeNeighborhood *makeNeighborhood = new MakeNeighborhood())
		: m_searchTree(),
		 
		  m_model(mo), 
		  m_numSol(0), m_numDom(0),

		  m_searchOutput(new SearchOutput()), 
		  m_inlineOutput(true),

		  m_chooseVar(SplitChooserPtr(new SplitChooser(new SearchRoundRobin))),
		  m_backTrack(StrategyPtr(backTrack)), 
		  m_move(StrategyPtr(move)),
		  m_makeNeighborhood(StrategyPtr(makeNeighborhood))
		  //, reduce_count(0)

#ifdef ELISA_PROFILE
		  , m_numSplit(0)
#endif
#ifdef ELISA_PROFILE_REDUCE
		  , m_reduceOut("reduce.log")
#endif
	{
		init();
	}

	/**
 	 * Constructor, where each solver is associated to a model
 	 * @param mo the model
 	 * @param size the size of the heap in bytes (default 256kb)
 	 * @param max the max number of boxes (default 2^16)
 	 */
	Solver(Model *mo, long size, long max,
		   BackTrack *backTrack = new BackTrack,
		   Move *move = new Move(), 
		   MakeNeighborhood *makeNeighborhood = new MakeNeighborhood())
	       //BackTrack *bts = 0, MoveStrategy *ms = 0, MakeNeighborhood *nb = 0)
		: m_searchTree(new Heap(size, max)),

		  m_model(mo), 
		  m_numSol(0), m_numDom(0),

		  m_searchOutput(new SearchOutput()), 
		  m_inlineOutput(true),

		  m_chooseVar(SplitChooserPtr(new SplitChooser(new SearchRoundRobin))),
		  m_backTrack(StrategyPtr(backTrack)), 
		  m_move(StrategyPtr(move)),
		  m_makeNeighborhood(StrategyPtr(makeNeighborhood))
		  //, reduce_count(0)

#ifdef ELISA_PROFILE
		  , m_numSplit(0)
#endif
#ifdef ELISA_PROFILE_REDUCE
		  , m_reduceOut("reduce.dat")
#endif
	{
		init();
	}

	/**
 	 * Destructor
 	 */
	virtual ~Solver ()
	{
		//delete _reduction;
		//delete _chooseVar;
		/*
		delete m_moveStrategy;
		delete m_backTrackStrategy;
		delete m_neighborhoodFunction;
		*/

		if (m_inlineOutput)
			delete m_searchOutput;
	}

public:
	//int reduce_count;

	/**
 	 * Runs a reduction step
 	 * return true if the model has been reduce
 	 */
	virtual bool reduce();

	/**
 	 * @brief Computes the next solution
 	 * @return false if there is no more solution
 	 */
	virtual bool next();

	/**
 	 * @brief Computes all remaining solutions
 	 * @return true if at least one solution has been computed since the first call
 	 */
	virtual bool solve();

	/**
 	 * @brief Returns the number of computed solutions
 	 */
	long numSolutions() const
	{
		return m_numSol;
	}

#ifdef ELISA_PROFILE
	/**
 	 * Returns the number of computed bisections.
 	 * Only available in profiling mode
 	 */
	long numSplit() const
	{
		return m_numSplit;
	}

	/**
 	 * Returns the number of processed boxes.
 	 * Only available in profiling mode
 	 */
	long numProcessedBoxes() const
	{
		return m_numDom;
	}
#endif // ELISA_PROFILE

	/**
 	 * Returns the search tree
 	 */
	SearchTree *getSearchTree()
	{
		return &m_searchTree;
	}

	const Model *getModel() const
	{
		return m_model;
	}

	Reduction *getReduction() const
	{
		return m_reduction.get();
	}

protected:
	/**
 	 * Initialization at the construction.
 	 */
	void init()
	{
		m_model->initVariableImplementation(m_searchTree);
		setReduction(m_model->createReduction());
		initVar();

		/*
		if (m_neighborhoodFunction == 0)
			m_neighborhoodFunction = new SplitMakeNeighborhood(&m_searchTree, m_chooseVar);

		if (m_backTrackStrategy == 0)
			m_backTrackStrategy = new BasicBackTrackStrategy(m_searchTree);

		if (m_moveStrategy == 0)
			m_moveStrategy = new FirstChildMoveStrategy(m_searchTree);
		*/
		m_makeNeighborhood->m_st = &m_searchTree;
		dynamic_cast<MakeNeighborhood *>(m_makeNeighborhood.get())->m_sc = m_chooseVar;
		m_backTrack->m_st = &m_searchTree;
		m_move->m_st = &m_searchTree;
	}


	/// Reset the counters before solving
	void reset()
	{
		//reduce_count = 0;
		m_numDom = 0;
		m_numSol = 0;
	}

	/**
 	 * Set the reduction used by the solver
 	 * @param c the new reduction
 	 */
	void setReduction(Reduction *c)
	{
		m_reduction = ReductionPtr(c);
	}

	/**
 	 * Use of a specific handler of boxes to be computed
 	 * @param m the handler to use
 	 */
	void useSearchOutput(SearchOutput & m)
	{
		if (m_inlineOutput) {
			delete m_searchOutput;
		}
		m_inlineOutput = false;
		m_searchOutput = &m;
	}

	/**
 	 * Set the search strategy used by the solver
 	 * @param c the new Strategy.
 	 */
	/*
	void setStrategy(ChoiceStrategy *c)
	{
	}
	*/

	/**
 	 * Use of a specific splitting strategy
 	 * @param c the searchChooserVar to use
 	 * @pre c doesn't contain any variables
 	 * @post c contains all variables of the model
 	 */
	void useChoiceStrategy(ChoiceStrategy *c)
	{
		m_chooseVar->setChoiceStrategy(c);
	}


	/**
 	 * @brief initialize SearchTree and SplitChooser
 	 *
 	 * each variable is added in the SplitChooser and linked
 	 * to the SearchTree
 	 */
	void initVar()
	{
		VarImplSet sv;
		m_model->toVariables(sv);
		std::for_each(sv.begin(), sv.end(), 
			boost::bind(&SplitChooser::insert, m_chooseVar, _1));
	}

	/**
 	 * tell if the current box is a solution
 	 */
	bool isSolution()
	{
		return m_chooseVar->isSolution();
	}

	/**
 	 * Choose a variable to split
 	 */
	VarImplPtr chooseVariable()
	{
		return m_chooseVar->get();
	}

	/// DATA

	// @var the model of constraints
	Model *m_model;

	// @var the model to be processed
	SearchTree m_searchTree;

	// @var number of computed solutions
	long m_numSol;

	// @var number of processed domains
	long m_numDom;

#ifdef ELISA_PROFILE
	// @var number of computed bisections
	long m_numSplit;
#endif

#ifdef ELISA_PROFILE_REDUCE
	std::ofstream m_reduceOut;
#endif

	typedef boost::shared_ptr<Reduction> ReductionPtr;

	/// ALGORITHMS

	// @var the reduction algorithm
	ReductionPtr m_reduction;

	// @var handler of computed solutions
	SearchOutput *m_searchOutput;
	bool m_inlineOutput;

	// @var choice of the variable to split
	SplitChooserPtr m_chooseVar;

	// @var a move strategy
	StrategyPtr m_move;

	// @var a backtrack strategy
	StrategyPtr m_backTrack;

	// @var a make neighborhood strategy
	StrategyPtr m_makeNeighborhood;
};

END_NAMESPACE_ELISA

#endif // ELISA_SOLVER_H
